package 并查集;

import java.util.Arrays;

public class DisjointSet {
    int[] s;

    public DisjointSet(int size) {
        this.s = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
        }
    }

    public int find(int x) {
        if (x == s[x]) {
            return x;
        }
        return s[x] = find(s[x]);  //路径压缩
    }

    public void union(int x, int y) {
        int a = find(x);
        int b = find(y);
        if (a == b) {
            return;
        }
        s[a] = b;
    }

    @Override
    public String toString() {
        return "DisjointSet{" +
                "s=" + Arrays.toString(s) +
                '}';
    }


    public static void main(String[] args) {
        //索引对应顶点
        // 元素是用来表示与之对应有关系的顶点
        DisjointSet set = new DisjointSet(5);
//        System.out.println(set);
//
//        set.union(1, 2);
//        System.out.println(set);
//        set.union(3, 4);
//        System.out.println(set);
        set.union(1, 3);
//
        System.out.println(set);


        set.find(1);

        System.out.println(set);
    }
}
